public class MergeSort {
    //实现归并排序
    public static void mergeSort1(int[]array){
        //调用归并排序的递归方法
        mergeSortChild1(array,0, array.length-1);
    }
    //归并排序的底层递归方法（使用递归时要求递归有以下三个参数，为保证接口统一性，在归并排序方法中调用此递归方法即可
    private static void mergeSortChild1(int[]array,int start,int end){
        //判断结束情况
        if(start>=end){
            return;
        }
        //向下递归分解为有序数组
        int mid=(start+end)/2;
        //向左递归分解
        mergeSortChild1(array,start,mid);
        //向右递归分解
        mergeSortChild1(array,mid+1,end);
        //合并分解完的数组
        merge1(array,start,mid,end);
    }

    //调用到的合并数组方法
    private static void merge1(int[]array,int start,int mid,int end){
        //创建一个新的数组作为模板
        int[]tmp=new int[end-start+1];
        //设定新数组的下标
        int k=0;
        //设定左右两个待合并的组的起始，终止下标
        int s1=start;
        int e1=mid;
        int s2=mid+1;
        int e2=end;
        //由于两个待合并的数组皆有序（从小到大顺序排放），所以直接比较两数组的起始元素，取出其中较小这放入模板数组中，对应下标后移
        while(s1<=e1&&s2<=e2){
            if(array[s1]<=array[s2]){
                tmp[k++]=array[s1++];
            }else{
                tmp[k++]=array[s2++];
            }
        }
        //循环结束说明某个数组已经遍历完毕，则另一个数组剩下元素都比模板数组中存储的元素大，直接将剩余元素存入其中即可
        while(s1<=e1){
            tmp[k++]=array[s1++];
        }
        while(s2<=e2){
            tmp[k++]=array[s2++];
        }
        //此时tmp数组中已经存储了二者合并完毕的内容，将其中内容拷贝到原数组中即可，注意对应下标
        for(int i=0;i<k;i++){
            array[i+start]=tmp[i];
        }
    }

    //实现归并排序的非递归形式
    public static void mergeSort2(int[]array){
        //认为数组已经按照单个元素为一组的方式分解完毕，开始合并
        //设定gap增量来获取合并数组的首、中、末，并且不断使gap扩倍，以此模拟递归算法中实现的合并方式
        int gap=1;
        while(gap<array.length){
            for(int i=0;i< array.length;i+=2*gap){
                int start=i;
                int mid=start+gap-1;
                //判断是否越界，越界直接置于末端
                if(mid>array.length-1){
                    mid= array.length-1;
                }
                //判断是否越界，越界直接置于末端
                int end=mid+gap;
                if(end>array.length-1){
                    end= array.length-1;
                }
                //合并数组
                merge2(array,start,mid,end);
            }
            //gap扩倍
            gap*=2;

        }
    }

    //调用到的合并数组方法
    private static void merge2(int[]array,int start,int mid,int end){
        //创建一个新的数组作为模板
        int[]tmp=new int[end-start+1];
        //设定新数组的下标
        int k=0;
        //设定左右两个待合并的组的起始，终止下标
        int s1=start;
        int e1=mid;
        int s2=mid+1;
        int e2=end;
        //由于两个待合并的数组皆有序（从小到大顺序排放），所以直接比较两数组的起始元素，取出其中较小这放入模板数组中，对应下标后移
        while(s1<=e1&&s2<=e2){
            if(array[s1]<=array[s2]){
                tmp[k++]=array[s1++];
            }else{
                tmp[k++]=array[s2++];
            }
        }
        //循环结束说明某个数组已经遍历完毕，则另一个数组剩下元素都比模板数组中存储的元素大，直接将剩余元素存入其中即可
        while(s1<=e1){
            tmp[k++]=array[s1++];
        }
        while(s2<=e2){
            tmp[k++]=array[s2++];
        }
        //此时tmp数组中已经存储了二者合并完毕的内容，将其中内容拷贝到原数组中即可，注意对应下标
        for(int i=0;i<k;i++){
            array[i+start]=tmp[i];
        }
    }
}
